package com.lyz.dataStructure.algorithm.dajiang2020;/**
 * @Author:759057893@qq.com Lyz
 * @Date: ${Date} 20:25
 * @Description:
 **/

import java.util.Scanner;

/*
2
2 2
10 1
20 2
3 4
10 2
18 3
10 2
 */

/**
 *@Author:759057893@qq.com Lyz
 *@Date: 2019/8/6 20:25
 *@Description:
 **/
public class Main2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int case1 = sc.nextInt();
        for(int k =0;k<case1;k++){
            int N = sc.nextInt();
            int M = sc.nextInt();
            int[] V = new int[N];
            int[] W = new int[N];
            int[][] C = new int[N+1][M+1];
            for(int j =0;j<N;j++){
                V[j] = sc.nextInt();
                W[j] = sc.nextInt();
            }
            for(int i =0;i<N+1;i++){
                C[i][0] = 0;
            }
            for(int i =0;i<M+1;i++){
                C[0][i] = 0;
            }
            for(int i =1;i<N+1;i++){
                for(int j =1;j<M+1;j++){
                    if(W[i-1]<=j){
                        C[i][j] = Math.max(C[i-1][j-W[i-1]]+V[i-1],C[i-1][j]);
                    }else {
                        C[i][j] = C[i-1][j];
                    }
                }
            }
            System.out.println(C[N][M]);
        }
    }
}
